package Fundamental.sort;

import java.util.Arrays;
/**
 * 假设数组 T ，它的长度是 i
 * 1. 第一次冒泡是将最大值移动到了最后一个位置 i-1
 * 2. 第二次冒泡是将第二大的值移动到了到数第二的位置 i - 2
 * */
// j < array.length -1 ，可以变化成 j < array.length -1 - i
// i 从 0 开始，最大的值是 array.length -2
// 最后一轮冒泡 j 到 1 , 也就后面 i - 1 位置上的值都是有序的了
// 没有加 -i 的情况下，
//compareCnt:16
//swapCnt:9
// 加了之后：
//compareCnt:10
//swapCnt:9
// 还可以加一个 boolean 类型的变量，如果前面没有发生交换，说明
// 前面的数据已经有序了，这样的话，就可以的省掉好多次循环了。
// 再没有设置 boolean 变量之前，
//bubleCnt:4
// 还可以进一步的优化，比较得次数，假设右侧有序的一份，本来就有序，是不是就不需要
// 再比较了。可以通过记录一趟冒泡过程中最后一次交换的位置，这个位就是下次比较截至位置。
public class BubbleSort {

    /**
     * 用来记录比较的次数。
     * */
    private static int compareCnt = 0 ;

    /**
     * 用来记录交换的次数。
     * */
    private static int swapCnt = 0 ;

    /**
     * 用来记录冒泡的次数的次数。
     * */
    private static int bubleCnt = 0 ;

    public static void sort(int[] array){
        boolean isSwap = Boolean.TRUE;
        // 最后一次交换的位置
        int lastSwapPosition = 0 ;

        for (int i = 0; i < array.length -1 ; ) {

            if(!isSwap){
               break;
            }
            bubleCnt++;
            for(int j = 0 ; j < array.length -1 - i ;j++){
                if(compare(array[j] , array[j+1]) ){
                    isSwap = Boolean.TRUE;
                    swap(array,j,j+1);
                    lastSwapPosition = j + 1;
                }else {
                    isSwap = Boolean.FALSE ;
                }
            }
            i += array.length - lastSwapPosition - 1;
        }
    }
    public static boolean compare(int a , int b){
        compareCnt++;
        return a > b ;
    }
    public static void swap(int[] array , int i , int j){
        swapCnt++;
        int swap = 0 ;
        swap = array[i];
        array[i] = array[j];
        array[j] = swap;
    }
    public static void main(String[] args) {
        int[] a = { -1 , -2 ,  8 ,2 ,1 , 3 , 4};

        System.out.println(Arrays.toString(a));
        sort(a);
        System.out.println("compareCnt:" + compareCnt);
        System.out.println("swapCnt:" + swapCnt);
        System.out.println("bubleCnt:" + bubleCnt);
        System.out.println(Arrays.toString(a));
    }
}
